﻿//https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.size();
        unordered_set<string> hash;
        for (auto& e : wordDict) hash.insert(e);
        s = '-' + s;

        vector<bool> dp(n + 1);
        dp[0] = true;

        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

//https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int lengthOfLIS(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);

        for (int i = 1; i < n; i++)
        {
            if (nums[i] > ret.back())
            {
                ret.push_back(nums[i]);
            }
            else
            {
                int left = 0, right = ret.size() - 1;
                while (left < right)
                {
                    int mid = (left + right) / 2;
                    if (ret[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                ret[left] = nums[i];
            }
        }

        return ret.size();

    }
};